﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 原题连接：https://leetcode.cn/problems/valid-parentheses/
/*
题目描述：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
 

示例 1：
输入：s = "()"
输出：true

示例 2：
输入：s = "()[]{}"
输出：true

示例 3：
输入：s = "(]"
输出：false
 

提示：
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成
*/

// 开始解题：
// 方法1——小题大做地使用栈
// 重定义数据类型
typedef char DataType;

// 定义栈结构
typedef struct stack {
	DataType* data;
	int top;
	int capacity;
} Stack;

// 栈的初始化
void StackInit(Stack* ps) {
	assert(ps);
	ps->data = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

// 压栈
void StackPush(Stack* ps, DataType x) {
	assert(ps);
	// 检查是否需要增容
	if (ps->top == ps->capacity) {
		int newCapacity = ps->capacity == 0 ? 10 : ps->capacity * 2;
		DataType* temp = (DataType*)realloc(ps->data, newCapacity * sizeof(DataType));
		if (NULL == temp) {
			perror("ralloc fail!\n");
			exit(-1);
		}
		ps->data = temp;
		ps->capacity = newCapacity;
	}
	ps->data[ps->top] = x;
	ps->top++;
}

// 弹栈
void StackPop(Stack* ps) {
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

// 栈的打印
void printStack(Stack* ps) {
	assert(ps);
	int i = 0;
	for (i = ps->top - 1; i >= 0; i--) {
		printf("[%d]\n", ps->data[i]);
	}
}

// 返回栈顶数据
DataType StackTop(Stack* ps) {
	assert(ps);
	assert(ps->top > 0);
	return ps->data[ps->top - 1];
}

// 返回栈的数据个数
int StackSize(Stack* ps) {
	assert(ps);
	assert(ps->top >= 0);
	return ps->top;
}

// 判断栈是否为空
bool StackEmpty(Stack* ps) {
	assert(ps);
	return ps->top == 0;
}

// 栈的销毁
void DestroyStack(Stack* ps) {
	assert(ps);
	free(ps->data);
	ps->data = NULL;
	ps->top = 0;
	ps->capacity = 0;
}



bool isValid(char* s) {
	Stack stack;
	StackInit(&stack);
	while (*s) {
		if (*s == '(' || *s == '[' || *s == '{') {
			// 如果当前遍历到的字符属于左括号，就将其入栈
			StackPush(&stack, *s);
		}
		else { // 如果遇到右括号，就要从栈中取出左括号进行匹配
			if (StackEmpty(&stack)) {
				// 遇到了右括号，但栈为空，说明前面已没有可匹配的左括号了，
				// 直接返回false即可
				DestroyStack(&stack);
				return false;
			}
			DataType top = StackTop(&stack);
			StackPop(&stack);
			if ((top == '(' && *s != ')')
				|| (top == '{' && *s != '}')
				|| (top == '[' && *s != ']')) {
				return false;
			}


		}
		s++;
	}
	// 如果遍历完后栈为空，说明已经完全匹配完了，答案是true
	// 如果不为空，说明还有的括号还为匹配，答案为false
	// 所以直接返回栈是否为空的结果即可。
	bool result = StackEmpty(&stack);
	DestroyStack(&stack);
	return result;
}